% !TeX spellcheck = fr-moderne
\chapter{Achitecture d'AbsCon} % Main chapter title

\label{Chapter5} % Change X to a consecutive number; for referencing this chapter elsewhere, use \ref{ChapterX}

\lhead{Chapitre 5. \emph{Achitecture d'AbsCon}} % Change X to a consecutive number; this is for the header on each page - perhaps a shortened title

Dans ce chapitre, nous allons présenter l'architecture du solveur AbsCon. Ce solveur permet de résoudre les CSPs binaires et non binaires. Il est implémenté en Java, il est donc indépendant du plate-forme. Ce solveur est intégré des heuristiques de recherche et des techniques de propagation. L'architecture d'AbsCon est d'abord abordée, ensuite, la résolution d'un CSP dans AbsCon est présentée. Puis, nous présentons comment la propagation se déroule pour les consistances : DC, SAC et PWC+GAC.

%----------------------------------------------------------------------------------------
%	SECTION 1
%----------------------------------------------------------------------------------------
\section{Les paquets dans AbsCon}
Dans AbsCon, nous trouvons les paquets principaux ci-dessous :
\begin{itemize}
\item \textbf{\textit{abscon}} : pour lancer le programme, initialiser le problème, le solveur
\item \textbf{\textit{problem.*}} : contenir les classe pour présenter un problème, tous les problèmes doivent étendre la classe "Problem"
\item \textit{\textbf{variable}} : pour définir les variables du problème
\item \textbf{\textit{variable.domain}} : pour définir le domaine de variables
\item \textbf{\textit{contraint.*}} : pour représenter les contraintes
\item \textbf{\textit{search.*, heuristic.*}} : les heuristiques, les algorithmes pour la recherche
\item \textbf{\textit{propagation.*}} : pour la propagation, il y a plusieurs types de propagation : AC, FC, SAC, \dots
\end{itemize}

%----------------------------------------------------------------------------------------
\section{Représentation d'un CSP}
Pour représenter un CSP sous AbsCon. Les classes utilisées sont \textit{Problem, Variable, Domain} and \textit{Constraint}. Un UML diagramme est donné par la figure ~\ref{fig:reprentationCSP}. 
\begin{figure}[ht]
	\centering
	\includegraphics[height=3cm]{./images/AbsCon/csp_representation.png}
	\caption{AbsCon: Représentation d'un CSP \cite{merchez2001abscon}}
	\label{fig:reprentationCSP}
\end{figure}

Dans AbsCon un problème est caractérisé par deux tableaux spécifiant un ensemble de variables et un ensemble de contraintes. La classe \textit{Problem} est une classe abstraire dont il est possible de dériver un classe représentant un problème spécifique. L'utilisateur doit outrepasser deux méthode (\textit{specifyVariables(), specifyConstraints()}) pour spécifier les variables et les contraintes. Une variable est caractérisée par un domaine et par un tableaux spécifiant l'ensemble des contraintes portant sur cette variable. Notez que la classe \textit{Variable} a une référence sur un objet \textit{ValueChooser} qui implémente une heuristique de choix de valeur. Un domaine est associé avec une variable et est caractérisé par un tableau spécifiant l'ensemble de valeurs autorisées. Une contrainte est caractérisé par un tableau de variable liant avec elle et par un ensemble de méthodes qui peut être appelé pendant la propagation.

%----------------------------------------------------------------------------------------
\section{Résolution d'un CSP}
\begin{figure}[ht]
	\centering
	\includegraphics[height=8cm]{./images/AbsCon/absconResolution.png}
	\caption{AbsCon: Résolution d'un CSP \cite{merchez2001abscon}}
\end{figure}

Nous décrivons dans cette section les classes utilisées pour résoudre un CSP. Ce sont : \textit{Solver, VariableChooser, ValueChooser} et \textit{Propagator}.

La classe \textit{Solver} se situe dans le paquet \textbf{search.*}. Elle implémente l'algorithme DFS (Depth First Search) avec Backtracking. Quand un objet de \textit{Solver} est créé, un spécifique CSP est associé avec lui. Cet objet gère l'ensemble d'assignation et essaie, à chaque pas, de faire une nouvelle assignation. La prochaine variable à assigner est choisie par un objet de \textit{VariableChooser} et la prochaine valeur à assigner est choisie par un objet de \textit{ValueChooser}. Après chaque nouvelle assignation, la propagation est appliquée par un objet de \textit{Propagation} . La résolution est arrêtée quand une (ou \textit{n}) solution est trouvé ou quand l'espace de recherche est totalement couverte. 

%\textbf{Solver} : se situe dans le paquet \textbf{search.*}. 
%	\begin{itemize}
%	\item Elle implémente l'algorithme DFS (Depth First Search) avec Backtracking.
%	\item Quand le solveur "solver" est créé, un CSP est associé avec lui.
%	\item Le solveur gère l'ensemble d'assignation et essaiment, à chaque pas faire une nouvelle assignation.
%	\end{itemize}
%\textbf{VariableChooser, ValueChooser} : se situent dans \textbf{heuristics.*} 
%	\begin{itemize}
%	\item Pour choisir la variable, la valeur à assigner dans chaque assignation.
%	\end{itemize}
%\textbf{Propagator} : se situe dans \textbf{propagation.*}
%	\begin{itemize}
%	\item Elle représente la méthode pour propagation, elle est liée avec la classe "Constraint" pour tester la consistance.
%	\item AC, FC, GT, BT, \dots
%	\end{itemize}

La classe \textit{VariableChooser} se situe dans le paquet \textbf{heuristics.*}. Elle représente une heuristique de choix de valeur attachée à une variable donnée. La classe \textit{VariableChooser} représente une heuristique de choix de variable tels que : \textit{Lexicographic, SmallestDomain (dom), SmallestDomainOnDegree (dom/deg)}. La classe \textit{Propagation} se situe dans le paquet \textbf{propagation.*}. Elle représente la méthode pour propagation, elle est liée avec la classe \textit{Constraint} pour tester la consistance. Dans AbsCon, des consistances ont été implémentées tels que : \textit{DC, forward checking, SAC, PWC + GAC,\dots} 

%----------------------------------------------------------------------------------------
\section{La propagation dans AbsCon}
Nous décrivons dans cette section la propagation dans AbsCon. Les paquets pour la propagation sont dans \textbf{propagation.*}. Quand on veut développer une propagation, il faut dériver la classe de base \textit{Propagation}. Dans cette classe, nous avons des méthodes de base qui sont utilisées pendant la résolution : 

\begin{itemize}
\item \textit{enforce()} : cette méthode est utilisée au départ, pour obtenir la consistance avant de faire la recherche.
\item \textit{enforceAfterAssignmentOf(Variable)} : pendant la recherche, après chaque assignation de variable, cette méthode est utilisée pour obtenir la consistance.
\item \textit{enforceAfterRefutationOf(Variable)} : si pendant la recherche une assignation est échouée, alors la valeur dans cette assignation est enlevée. Cette méthode est appelée pour achever la consistance.
\item \textit{propagate()} : pour obtenir la consistance dans trois méthodes précédentes, \textit{propagate()} est appelée. L'idée de \textit{propagate()} est décrite ci-dessous.
\end{itemize}

%\begin{lstlisting} [caption= méthode propagate()]
%Propagation.propagate()
%// OUT : reviser tous les variables dans la queue et enlever les inconsistances
%  Prendre chaque variable $x$ dans la queue
%    Pour chaque contrainte $c$ portant sur $x$
%      Appeler $c.filter($x$)$
%\end{lstlisting}
 
\begin{lstlisting} [caption= méthode propagate()]
function Propagation.propagate()
// OUT : reviser tous les variables dans la queue et enlever les inconsistances
   For each $x$ $\in Q$
      For each $c_i$ s.t. $x \in vars(c_i)$
         $c_i.filterFrom($x$)$
\end{lstlisting}

La propagation dans AbsCon est orientée variables, signifiant que la queue \textit{Q} utilisée pour la propagation contient des variables. Quand une variable $x$ est choisie dans \textit{Q}, toutes les contraintes portant sur $x$ sont sollicitées pour filtrer ($c_i.filterFrom(x)$). La méthode $c_i.filterFrom(x)$ va réviser la consistance pour tous les variables dans $c$. Lorsqu'elle détecte l'inconsistance d'une valeur, cette valeur est enlevé et la variable est mise dans la queue. Les sections suivantes vont présenter quelques algorithmes de propagation dans AbsCon.


%----------------------------------------------------------------------------------------
\section{DC}

La propagation de DC(ou AC) est définie dans la classe \textit{AC} sous le paquet \textbf{propagation.*}. Elle étend la classe \textit{Propagation}. Pour obtenir la DC les fonctions suivantes sont appelées : 
\begin{itemize}
\item \textit{enforce()} : 	cette méthode est appelée au départ (avant la recherche) pour forcer la consistance. Elle met tous les variables dans la queue, ensuite appelle la méthode propagate() pour forcer la DC.

\item \textit{enforceAfterAssiggmentOf(Variable)} : cette méthode est appelé pendant la recherche après chaque assignation, la variable assigné est mise dans la queue et la fonction propagate() est appelé pour forcer la consistance.

\item \textit{enforceAfterRefutationOf(Variable)} : cette méthode est appelé pendant la recherche, quand une assignation est échouée, la valeur est enlevée, la variable est mise dans la queue et la fonction propagate()  est appeler pour la DC.

\end{itemize}



%----------------------------------------------------------------------------------------
\section{SAC}

La classe \textit{SAC} étend la classe \textit{StrongConsistency} qui étend la classe \textit{AC}. Elle est dans le paquet \textbf{propagation.*}. L'idée de StrongConsistency est d'ajouter la méthode \textit{enforceMore()} dans les méthodes \textit{enforce(), enforceAfterAssiggmentOf(Variable), enforceAfterRefutationOf(Variable)}. La méthode \textit{enforeMore()} va examiner la consistance pour chaque future variable (les variables non assignées) par la méthode \textit{makeSingletonTestOn(Variable)} dans la classe SAC. La méthode \textit{makeSingletonTestOn(Variable)} teste  le SAC pour chaque valeur d'une variable, l'enlève si elle ne satisfait pas. Elle s'arrêter quand il y a plus de changement, quand il y a le changement, on redémarre \textit{enforceMore()}.



%----------------------------------------------------------------------------------------
\section{PWC+GAC}

L'algorithme PWC+GAC est implémenter par deux classes : \textit{PWCGAC} et \textit{ConstraintHardExtensionPWCGAC}. La classe \textit{PWCGAC} étend la classe \textit{AC}. Elle permet de propager les contraintes nécessaires pour obtenir la consistance. Quand la propagation \textit{PWCGAC} est créée, elle va trouver les intersections entre les contrainte de type \textit{ConstraintHardExtensionPWCGAC} et les ajouter dans ces contraintes. Ce processus est nécessaire pour examiner l'extensibilité des tuples. Pendant la propagation, la méthode \textit{propagate()} est appelée. Et puis elle appelle la méthode \textit{ConstraintHardExtensionPWCGAC.runPropagator(Variable)} pour réviser la consistance PWC+GAC. L'idée de cette méthode est décrite ci-dessous.\\

%\textit{ConstraintHardExtensionRPWC.runPropagator(Variable)}
\begin{lstlisting} [caption= méthode runPropagator()]
function $c$.runPropagator(Variable)
// OUT:enlever les tuples invalides, ne pas s'etendre aux autres tuples
//     enlever les valeurs inconsistantes du domaine de variable
     for each tuple $\tau \in rel(c)$
       if $\tau$ is not valid or $\tau$ can not extend to others constraints
          remove $\tau$
     update domain of variables in $c$
\end{lstlisting}

Nous avons présenté dans ce chapitre la structure d'AbsCon, la résolution d'un CSP et la propagation dans CSP. Cette partie nous permet de comprendre les démarches dans AbsCon et d'implémenter les algorithmes de consistances fortes dans le chapitre suivant.

%----------------------------------------------------------------------------------------

